/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhong
 *
 */
public class AmbiguousCoordinates {
	public List<String> ambiguousCoordinates(String S) {
		int n = S.length();
		List<String> res = new ArrayList<>();
		for (int i = 1; i < n - 2; i++) {// 分割点
			List<String> left = help(S.substring(1, i + 1));
			List<String> right = help(S.substring(i + 1, n - 1));
			if (left.isEmpty() || right.isEmpty()) {
				continue;
			}
			for (String lString : left) {
				for (String rString : right) {
					res.add("(" + lString + ", " + rString + ")");
				}
			}
		}
		return res;
	}

	private List<String> help(String substring) {
		List<String> reStrings = new ArrayList<>();
		int n = substring.length();
		// 放置小数点的可能：有前置0，则只有0或1种可能
		boolean lastZero = substring.charAt(n - 1) == '0';// 有后置0，则不能是小数
		if (substring.charAt(0) == '0') {
			if (lastZero && n != 1) {
				return reStrings;
			}
			// 检查不是全部0
			boolean allZero = true;
			for (int j = 1; j < substring.length(); j++) {
				if (substring.charAt(j) != 0) {
					allZero = false;
					break;
				}
			}
			if (!allZero) {
				String e = "0." + substring.substring(1);
				reStrings.add(e);
				return reStrings;
			}
		}
		reStrings.add(substring);
		if (lastZero) {
			return reStrings;
		}
		// 否则，可以在任意位置增加小数点
		for (int j = 0; j < substring.length() - 1; j++) {
			String string = substring.substring(0, j + 1) + "." + substring.substring(j + 1);
			reStrings.add(string);
		}
		return reStrings;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String S = "(123)";// "(100)";// "(0123)";// "(00011)"; // "(123)";
		System.out.println(new AmbiguousCoordinates().ambiguousCoordinates(S));
	}

}
